package bird.queue.linkedlist_queue;


import bird.queue.Queue;

/**
 * @author sijunqiang
 * @data 2021/5/26 7:58
 * @description: 自定义基于链表实现的队列
 * 一般情况下：链表的在尾部添加元素或者删除元素时间复杂度是O(n)的。
 * 所以才引出了一个新的概念 带有尾指针的链表
 */
public class LinkedListQueue<E> implements Queue<E> {

    // head-代表指向队首的节点
    private Node head;

    // tail-代表指向队尾的节点
    private Node tail;

    // size-代表队列中实际存储的元素个数
    private int size;

    // 内部节点 链表中数据真正存储的地方
    private class Node {
        // 真正存储元素的地方
        public E data;

        // 指向下一个节点的指针 若指向下一个节点的指针为null 说明是链尾
        public Node next;


        public Node(E e, Node next) {
            this.data = e;
            this.next = next;
        }

        public Node(E e) {
            this(e, null);
        }

        public Node() {
            this(null, null);
        }

        @Override
        public String toString() {
            return data.toString();
        }
    }

    /*思路：
     *   从head端删除元素
     *   从tail端添加元素
     *    这样的话就能保证 出队和入队的时间负载度为O(1)
     * head-端的新增/删除 时间复杂度是0(1)
     * */
    @Override
    public void enqueue(E e) {
        // 当队列为空的时候 此时head==tail==null
        if (tail == null) {
            tail = new Node(e);// 在队尾添加一个新的节点
            head = tail; // 将head指针指向新的节点
        } else {
            tail.next = new Node(e);// 在队尾添加一个新的节点
            tail = tail.next; // 将tail这个指向尾节点的指针重新指向最后一个节点
        }
        size++;
    }

    /*
     * 出队的思路：从队列的队首出队
     * */
    @Override
    public E dequeue() {
        // 先判断队列是否为空
        if (isEmpty()) {
            throw new IllegalArgumentException("cannot dequeue! ");
        }
        Node retNode = head;//将头节点赋值给一个新的临时节点变量
        head = head.next; // 将头节点的下一个节点 作为新的节点
        retNode.next = null;// 删除第一个节点

        if (head == null) {//如果队列只有一个元素的话 那么尾节点也需要置为null
            tail = null;
        }
        size--;
        return retNode.data;
    }

    @Override
    public E getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("queue is empty!");
        }
        return head.data;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public Boolean isEmpty() {
        return size == 0;
    }


    @Override
    public String toString() {

        StringBuilder res = new StringBuilder();

        res.append("Queue: front:");
        Node cur = head;
        while (cur != null) {
            res.append(cur + "->");
            cur = cur.next;
        }
        res.append("NULL tail");
        return res.toString();
    }
}
